package leetcode_600;




/**
 *@author 周杨
 *FreedomTrail_514_ 轮转解决一个字符串遍历问题
 *describe:用动态规划dp[i][j] 本次处于i为12点 j为key遍历到的位置  每次选取最小 AC 20%
 *2018年9月9日 下午2:02:38
 */
public class FreedomTrail_514_ {
	 public int findRotateSteps(String ring, String key) {
		 int n = ring.length();
	        int m = key.length();
	        int[][] dp = new int[m + 1][n];
	        
	        for (int i = m - 1; i >= 0; i--) {
	            for (int j = 0; j < n; j++) {
	                dp[i][j] = Integer.MAX_VALUE;
	                for (int k = 0; k < n; k++) {
	                    if (ring.charAt(k) == key.charAt(i)) {
	                        int diff = Math.abs(j - k);
	                        int step = Math.min(diff, n - diff);
	                        dp[i][j] = Math.min(dp[i][j], step + dp[i + 1][k]);
	                    }
	                }
	            }
	        }
	        
	        return dp[0][0] + m;
	 }
	
}
